The arithmetic unit is one of the most important components of any integrated electronic data processing system. Arithmetic units perform a wide variety of mathematical functions upon operands which are transmitted from other portions of an integrated system. The basic addition, subtraction and multiplication functions are quickly and efficiently performed in arithmetic units today. However, presently available techniques for performing the exact square root function have not been completely satisfactory with respect to efficiency and speed.
The term exact square root is used to describe results equivalent to those produced by the common longhand square root process, i.e., a positive value for the partial root and a "remainder" which, if non negative, is strictly less than twice the partial root plus one unit in the last place (or twice the root minus one, if negative), such that, in infinite precision, the sum of the partial root squared and the remainder is exactly equal to the operand.
An exact square root provides a result more useful than an approximate square root of bounded error. The exact square root provides the basis for implementation of infinitely precise roundings such as specified by IEEE-754-1985. Furthermore, the partial root and remainder composing the exact square root provides a starting point for initiating subsequent higher precision determination of an exact square root without reference to the original operand. Neither of these features are obtained from an approximate square root of bounded but indeterminant error.
One technique to find the exact square root is a binary version of the common longhand square root method. This method suffers from the drawback that each iteration contributes only 1 to 3 bits of the partial root and requires many iterations as the precision of the operand is increased. However, it does produce an exact square root suitable for precise rounding.
Another currently available system employs a square root method using a Newton-Raphson approximation technique. In this system, an approximation of the reciprocal of the root is calculated using an iterative process to achieve an approximate value for the reciprocal in a full precision format. The full precision reciprocal approximation is then multiplied by the full precision operand to achieve a full precision estimate of the root. Only a bound on the indeterminate error of the estimated root is known and this information is inadequate for implementation of precise rounding. To obtain the exact square root, the indeterminacy in the error is removed by a second full precision multiplication. In the second full precision multiplication step, the approximate root is multiplied by itself and an exact difference is computed between the operand and the approximate root squared. This information is then sufficient to allow for recovery of the remainder and/or to obtain appropriate precise rounding procedures. Thus, the Newton-Raphson exact square root requires two full precision multiplies which are time consuming.
Therefore, a need has arisen for a system which uses a square root process which results in an exact square root which can be used for appropriate precise rounding procedures, but which is less time consuming than and more efficient than previously developed systems.